package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-18 20:35
 */
public class StealHouse {
    public static void main(String[] args) {

    }

    /**LeetCode 198
     * 五部曲：1.dp[i]i及之前的元素中选择的最大值 2.递推公式：dp[i]=max(nums[i]+dp[n-2],dp[n-1])3.初始化:对于0而言，只能是nums[0],对于1而言，
     * 取两种中的最大值4.遍历顺序：从前往后
     * @param nums
     * @return
     */
    public int maxOfSteal(int[]nums){
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        //创建dp数组
        int[]dp=new int[nums.length];
        //初始化
        dp[0]=0;
        dp[1]=Math.max(nums[0],nums[1]);
        //进行遍历
        for (int i = 2; i < nums.length; i++) {
            dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        //最后返回结果
        return dp[nums.length-1];
    }
}
